// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-07 10:23
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class AverageOfLevels {
    /**
     * 计算二叉树每一层的平均值
     */
    public List<Double> averageOfLevels(TreeNode root) {
        // 使用二叉树的层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 用于存储二叉树的每一层平均值
        List<Double> ans = new ArrayList<>();
        queue.offer(root);
        int layer = 1;
        int nLayer = 0;
        // 用于动态的存储每一层节点的个数
        double n = 1;
        double sum = 0;
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            sum += p.val;
            layer--;
            if (p.left != null) {
                queue.offer(p.left);
                ++nLayer;
            }
            if (p.right != null) {
                queue.offer(p.right);
                ++nLayer;
            }
            if (layer == 0) {
                // 当前节点遍历完毕
                // 因为layer是动态减少的，所以使用局部变量n对每一层节点的数量进行存储
                layer = nLayer;
                nLayer = 0;
                ans.add(sum / n);
                n = layer;
                sum = 0;
            }

        }
        return ans;
    }
}
